﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int> >& vw)
    {
        //动态表示：dp[i][j]表示选择前i个物品，体积不超过j的最大价值
        //动态转移方程：dp[i][j] = dp[i-1][j] 不选择i物品 dp[i][j] = dp[i-1][j-v[i]] + w[i] 选择i物品
        //初始化：dp[0][j] = dp[i][0] = 0
        //填表顺序：从上到下，从左到右
        //返回值：dp[n][V]

        vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
        for (int i = 1; i < n + 1; ++i)
        {
            for (int j = 1; j < V + 1; ++j)
            {
                if (j >= vw[i - 1][0])
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][V];
    }
};

class Solution {
public:
    /**
        * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
        *
        * 计算01背包问题的结果
        * @param V int整型 背包的体积
        * @param n int整型 物品的个数
        * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
        * @return int整型
        */
    int knapsack(int V, int n, vector<vector<int> >& vw)
    {
        //滚动数组优化
        vector<int> dp(V + 1);
        for (int i = 1; i < n + 1; ++i)
        {
            for (int j = V; j >= vw[i - 1][0]; --j)//这里j可能不会减到0，只会减到vw[i-1][0]，所以时间也有常熟量优化
            {
                dp[j] = max(dp[j], dp[j - vw[i - 1][0]] + vw[i - 1][1]);
            }
        }

        return dp[V];
    }
};

/*
描述
已知一个背包最多能容纳体积之和为v的物品
现有 n 个物品，第 i 个物品的体积为 vi , 重量为 wi
求当前背包最多能装多大重量的物品?
数据范围：1≤v≤1000 ，1≤n≤1000,1≤vi ≤1000 ，1≤wi≤1000
进阶 ：O(n⋅v)

示例1
输入：
10,2,[[1,3],[10,4]]
返回值：
4

说明：
第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4
*/

